package com.leetcode.offer;

/**
 * @author zfl
 * @Classname Search
 * @Description 在排序数组中查找数字
 * @Date 2020/11/27 15:26
 */
public class Search {

    /**
     * @param nums
     * @param target
     * @return
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.4 MB, 在所有 Java 提交中击败了72.42%的用户
     */
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;
        if(right == 0) {
            if(nums[0] == target) {
                return 1;
            }else {
                return 0;
            }
        }
        while (left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else if (nums[mid] > target) {
                right = mid - 1;
            }else {
                left = mid - 1;
                right = mid + 1;
                int count = 1;
                while (left >= 0) {
                    if(nums[left] == target) {
                        left--;
                        count++;
                    }else {
                        break;
                    }
                }
                while (right <= nums.length - 1) {
                    if(nums[right] == target) {
                        right++;
                        count++;
                    }else {
                        break;
                    }
                }
                return count;
            }
        }
        return 0;
    }
}
